package 优先级队列堆;

import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/last-stone-weight/description/
 * 最后一块石头的重量
 */
public class likou1046 {
    // 练习
    public int lastStoneWeight(int[] stones) {
        // 创建一个大跟堆. 利用 lambda 表达式
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        // 1. 遍历数组, 丢入到堆中.
        for (int stone : stones) {
            // add 调用的也是 offer() 方法
            heap.add(stone);
        }

        // 2. 模拟: 长度有两个以上才可以. 然后遍历堆, 取出最大的进行相碰
        while(heap.size() > 1) {
            int y = heap.poll();
            int x = heap.poll();
            if(y - x > 0) heap.offer(y - x);
        }
        return heap.isEmpty()  ? 0 : heap.poll();
    }

    // 练习
    public int lastStoneWeight2(int[] stones) {
        // 创建一个大跟堆. 利用 lambda 表达式
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        // 遍历数组, 丢入到堆中.
        for (int stone : stones) {
            // add 调用的也是 offer() 方法
            heap.add(stone);
        }
        // 然后遍历堆, 取出最大的进行相碰
        int large = 0, small = 0;
        while(!heap.isEmpty()) {
            large = heap.poll();
            // 第二个不一定有, 所以需要判断一下
            if(!heap.isEmpty()) {
                small = heap.poll();
                if(large - small > 0) heap.add(large - small);
            }
        }
        return large == small ? 0 : large;
    }

}
